El problema consiste en determinar la cantidad de substrings distintos que
pueden formarse con una cadena de caracteres. El input contiene un conjunto de
cadenas, y se debe calcular para cada una la cantidad de substrings distintos.

Si tenemos una cadena $s$, podemos obtener un substring $s_{ij}$ (con $1
\le i \le j \le |s|$) conociendo el sufijo $s_i$, y tomando luego su prefijo
$s_{i_j}$. Además, resulta fácil ver que si tenemos dos sufijos $s_{k1}$ y
$s_{k2}$ ($1 \le k1 \le k2 \le |s|$), si la primer letra del primer sufijo es
distinta a la primer letra del segundo sufijo, entonces los prefijos de esos
sufijos serán todos diferentes entre sí. En cambio si existe un prefijo $p$
en común, los sufijos tendrán $|p|$ prefijos en común, lo que significa
que ambos comparten $|p|$ substrings iguales. Por tanto, la cantidad de
subcadenas distintas que ambos sufijos generan será igual a $|s_{k1}| + |s_{k1}|
-|p|$. Esta es la idea del algoritmo que usamos para resolver este problema.

La estructura de datos que facilita la implementación de dicha idea es {\sl
suffix array}. Calculamos el {\sl suffix array} de la cadena, y luego el {\sl
Longest Common Prefix} (LCP {\sl array}), con el que calculamos la cantidad de
substrings que comparte cada par de sufijos (lo que equivale al valor de $|p|$).

Utilizamos una implementación de {\sl suffix array} basada en la presentada
en el paper de Toru Kasai\cite{kasai}, que en cada iteración aprovecha la
información obtenida en los iteraciones anteriores, de forma que en cada
paso conoce el doble de la información que en el anterior, logrando realizar
el ordenamiento en $\log(n)$ pasos. Para calcular el LCP utilizamos el
algoritmo de Sadakane, que calcula el LCP de un suffix array dado en tiempo
lineal sobre la cantidad de sufijos\cite{sadakane}.

Finalmente, para devolver la cantidad de substrings distintos,
calculamos la cantidad total de substrings de la cadena, que es
$\displaystyle\frac{|s|(|s|+1)}{2}$, y le restamos la sumatoria del arreglo
de LCP, que se corresponde con la cantidad total de substrings repetidos.
Intuitivamente, esto es lo mismo que recorrer el suffix array en orden inverso
(ya que el LCP array guarda los prefijos repetidos con el siguiente sufijo del
arreglo), sumando la longitud del sufijo actual y restando los substrings
repetidos que este sufijo produce con respecto a los anteriores iterados.
Es decir, en la i-ésima iteración, se suma la longitud del i-ésimo elemento
del suffix array y se resta su LCP que se corresponde con la cantidad de substrings
repetidos con el inmediato anterior, y no hace falta restar los repetidos con los
anteriores restantes pues ya fueron exluídos en las iteraciones previas.

\subsection*{Detalles de implementación}
La implementación del algoritmo de armado del suffix array con LCP fue sacada de:

http://trucosos.alwaysdata.net/snippets/173/

Fue testeada, verificada y se le agregó:
\begin{itemize}
\item El parseo de varios casos de test para un input dado.
\item La devolución del resultado en long long int.
\item El método sumatoria que se encarga de sumar los enteros de un arreglo y
devolver un long long int.
\end{itemize}

\subsection*{Análisis de complejidad}

Ambos algoritmos fueron vistos en clase. El orden para calcular el {\sl
suffix array} es $O(n\log^2(n))$, y calcular su LCP (igual que recorrerlo)
toma tiempo $O(n)$. El orden total del algoritmo resulta $O(n\log^2(n))$.
